P5504 [JSOI2011]柠檬

可以看出,选出区间的端点大小必须相同,不然可以将一端分在其他区间里,答案不会更劣。

dpidp_i 表示前 ii 个贝壳能得到的最大柠檬数, posipos_i 表示第 ii 个贝壳是第几个这种颜色的贝壳。

那么有转移:

dpi=max{dpj1+si(posiposj+1)2}dp_i=\max\{ dp_{j-1} + s_i(pos_i -pos_j+1)^2\}

dpi=max{dpj1+siposj22siposiposj2siposj}+si(posi+1)2dp_i=\max\{ dp_{j-1} + s_i{pos_j}^2-2s_ipos_ipos_j-2s_ipos_j\}+ s_i (pos_i+1)^2

假设两个决策 j<kj<k , 且 jj 优于 kk

dpj1+siposj22siposiposj2siposj>dpk1+siposk22siposiposk2siposkdp_{j-1} + s_i{pos_j}^2-2s_ipos_ipos_j-2s_ipos_j > dp_{k-1} + s_i{pos_k}^2-2s_ipos_ipos_k-2s_ipos_k

(dpj1+siposj22siposj)(dpk1+siposk22siposk)>2siposi(posjposk)(dp_{j-1} + s_i{pos_j}^2-2s_ipos_j ) - (dp_{k-1} + s_i{pos_k}^2-2s_ipos_k )> 2s_ipos_i (pos_j-pos_k)

(dpj1+siposj22siposj)(dpk1+siposk22siposk)si(posjposk)<2posi\frac{(dp_{j-1} + s_i{pos_j}^2-2s_ipos_j ) - (dp_{k-1} + s_i{pos_k}^2-2s_ipos_k )}{s_i(pos_j-pos_k)}< 2pos_i

因为最大值在队尾取到,所以用单调栈维护。

#include <cstdio>
#include <vector>
using namespace std;
#define LL long long
#define Lint long long
#define Top Stk[ s[ i ] ][ Stk[ s[ i ] ].size() - 1 ]
#define STop Stk[ s[ i ] ][ Stk[ s[ i ] ].size() - 2 ]

const int MAXN = 100000 , MAXC = 10000;
int n , s[ MAXN + 5 ] , pos[ MAXN + 5 ] , last[ MAXC + 5 ];
vector< int > Stk[ MAXC + 5 ];
LL dp[ MAXN + 5 ];

LL fx( int k , int i ) { return 1ll * s[ k ] * pos[ i ]; }
LL fy( int k , int i ) { return dp[ i - 1 ] + 1ll * s[ k ] * pos[ i ] * pos[ i ] - 2ll * s[ k ] * pos[ i ]; }
LL deltax( int k , int i , int j ) { return fx( k , i ) - fx( k , j ); }
LL deltay( int k , int i , int j ) { return fy( k , i ) - fy( k , j ); }

int main( ) {
	scanf("%d",&n);
	for( int i = 1 ; i <= n ; i ++ ) {
		scanf("%d",&s[ i ]);
		pos[ i ] = pos[ last[ s[ i ] ] ] + 1;
		last[ s[ i ] ] = i;
	}
	
	for( int i = 1 ; i <= n ; i ++ ) {
		for( ; Stk[ s[ i ] ].size() >= 2 && (Lint)deltay( i , STop , Top ) * deltax( i , Top , i ) <= (Lint)deltay( i , Top , i ) * deltax( i , STop , Top ) ; Stk[ s[ i ] ].pop_back() );
		Stk[ s[ i ] ].push_back( i );
		for( ; Stk[ s[ i ] ].size() >= 2 && (Lint)deltay( i , STop , Top ) >= (Lint)2 * pos[ i ] * deltax( i , STop , Top ) ; Stk[ s[ i ] ].pop_back() );
		dp[ i ] = dp[ Top - 1 ] + 1ll * s[ i ] * ( pos[ i ] - pos[ Top ] + 1 ) * ( pos[ i ] - pos[ Top ] + 1 );
	}
	
	printf("%lld\n", dp[ n ] );
	return 0;
}